//
// Description: 240. 搜索二维矩阵 II
// Created by Loading on 2021/10/25.
//

#include <bits/stdc++.h>

using namespace std;

/* 右上角向左下角遍历 */
bool searchMatrix_Z(vector<vector<int>> &matrix, int target) {
    int m = matrix.size(), n = matrix[0].size();
    int x = 0, y = n - 1;
    while (x < m && y >= 0) {
        if (matrix[x][y] == target) {
            return true;
        }
        if (matrix[x][y] > target) {
            --y;
        } else {
            ++x;
        }
    }
    return false;
}

/* 二分查找 */
bool searchMatrix(vector<vector<int>> &matrix, int target) {
    for (auto &v : matrix) {
        auto it = lower_bound(v.begin(), v.end(), target);
        if (it != v.end() && *it == target) {
            return true;
        }
    }

    return false;
}

int main() {
    vector<vector<int>> matrix = {{1, 2, 3},
                                  {4, 5, 6},
                                  {7, 8, 9}};
    int target = 5;
    bool res = searchMatrix(matrix, target);
    cout << res << endl;
    res = searchMatrix_Z(matrix, target);
    cout << res << endl;

    return 0;
}